package com.njupt.DynamicProgramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/2 13:47
 * @Description: 416. 分割等和子集
 * @Version: 1.0
 */


public class CanPartition_416 {

    public boolean isSplit = false;


    /**
     * 动态规划求解
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 != 0){
            return false;
        }else {
            sum /= 2;
        }
        //初始化dp数组
        int[] dp = new int[200*100+1];

        //0-1背包
        for (int i = 0; i < nums.length; i++) { //遍历物品
            for (int j = sum; j >= nums[i] ; j--) {  //遍历背包
                dp[j] = Math.max(dp[j],dp[j-nums[i]] + nums[i]);
            }
        }
        if(dp[sum] == sum){
            return true;
        }
        return false;
    }

    public boolean canPartition1(int[] nums) {
        int startIndex = 0;
//        List<Integer> result = new ArrayList();
//        backtracing(nums,startIndex,result);

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 != 0){
            return isSplit;
        }else {
            sum /= 2;
        }
        int result = 0;
        backtracing1(startIndex,result,nums,sum);

        return isSplit;
    }

    public void backtracing1(int startIndex,int result,int[] nums,int sum){
        if(startIndex == nums.length){
            return;
        }

        if(sum == result){
            isSplit = true;
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            result += nums[i];
            backtracing1(i+1,result,nums,sum);
            result -=nums[i];
        }
    }


    /**
     * 暴力法
     * @param nums
     * @param startIndex
     * @param result
     */
    private void backtracing(int[] nums, int startIndex, List<Integer> result) {

        if(startIndex == nums.length){
            return ;
        }

        int sumLeft = 0;
        int sumRight = 0;

        List<Integer> listCopy = new ArrayList<Integer>(Arrays.stream(nums).mapToObj(Integer::valueOf).collect(Collectors.toList()));
        for (int i = 0; i < result.size(); i++) {
            sumLeft += result.get(i);
            listCopy.remove(result.get(i));
        }


        for (int i = 0; i < listCopy.size(); i++) {
            sumRight += listCopy.get(i);
        }
        if(sumLeft > sumRight){
            return;
        }
        if(sumLeft == sumRight){
            isSplit = true;
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            result.add(nums[i]);
            backtracing(nums,i+1,result);
            result.remove(result.size()-1);
        }

    }


    public static void main(String[] args) {
        int[] nums = {1,5,11,5};
        CanPartition_416 test = new CanPartition_416();
        System.out.println(test.canPartition(nums));
    }
}
